Да ли је бипартитан
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,1 s | 64 Mb | стандардни излаз | стандардни улаз |
Пера je отишао на летњи спортски камп и када је тамо дошао видео је још неколико својих другара. И друга деца су знала понеког. Интересантно, Пера је свако дете знао посредно (знао је некога, ко зна некога, ко зна некога итд. ко зна то дете).
Потребно је да се деца поделе у две групе, али пошто свако жели да упозна што више нових другара, потребно је да сваку групу чине међусобно непознате особе (две особе које се већ познају не могу бити у истој групи). Написати програм који одређује да ли је то могуће и ако јесте, која ће све деца бити у групи са Пером.
Улаз
Са стандардног улаза се учитава број деце \(n\) (\(1 \leq n \leq 10^5\)), а затим и број парова \(m\) деце која се већ познају (\(0 \leq m \leq \frac{n(n-1)}{2}\)), а затим и низ парова бројева од \(0\) до \(n-1\) који представљају познанства.
Излаз
На стандардни излаз исписати редне бројеве деце који су у групи са
Пером (кренувши од Пере који има редни број 0, па у растуће поретку) или
симбол - ако тражене две групе није могуће формирати.
Пример 1
Улаз
6 6 0 1 1 2 2 3 3 4 4 5 5 0
Излаз
0 2 4
Објашњење
Ако су у једној групи деца са бројевима 0, 2 и 4, у другој су деца са бројевима 1, 3 и 5 и тада се ни у једној групи не налазе деца која се међусобно познају.
Пример 2
Улаз
5 5 0 1 1 2 2 3 3 4 4 0
Излаз
-
Објашњење
Пера (особа 0) не сме да буде у групи са особом 1, која не сме да буде у групи са особом 2, што значи да 0 и 2 морају да буду у истој групи. Особе 2 и 3 не могу да буду у истој групи, па су 1 и 3 у истој групи. Особа 4 не сме да буде у групи са особом 3, па она мора бити у групи са особама 0 и 2, међутим, то није допуштено, јер се особе 4 и 0 познају.
Морате бити улоговани како бисте послали задатак на евалуацију.